Extended Euclidean Algorithm

释义 Definition（中文）

扩展欧几里得算法：在计算两个整数 (a) 和 (b) 的最大公约数 (\gcd(a,b)) 的同时，求出整数 (x, y)，使得满足贝祖等式：
[ ax + by = \gcd(a,b) ]
它常用于求模逆元、解线性丢番图方程等。（除“求最大公约数”外，“扩展”之处在于还返回系数 (x,y)。）

发音 Pronunciation（IPA）

/ɪkˈstɛndɪd juːˈklɪdiən ˈælɡəˌrɪðəm/

例句 Examples

The extended Euclidean algorithm finds the gcd and the coefficients (x) and (y).
扩展欧几里得算法能求最大公约数，并给出系数 (x) 和 (y)。

In RSA, we use the extended Euclidean algorithm to compute the modular inverse needed for the private key.
在 RSA 中，我们用扩展欧几里得算法计算生成私钥所需的模逆元。

词源 Etymology（中文）

“Euclidean”源自古希腊数学家欧几里得（Euclid），其《几何原本》奠定了古典数学传统；“algorithm”一词与中世纪学者花剌子密（al-Khwārizmī）的名字相关，后来在欧洲语言中演变为“算法”。“extended（扩展的）”强调：不仅执行欧几里得算法的辗转相除来求 (\gcd)，还“扩展”到回代过程，得到满足贝祖等式的系数。

相关词 Related Words

• Algorithm
• Euclidean
• Gcd
• Bézout’s-identity
• Modular-inverse
• Diophantine-equation
• Modulo
• Coprime
• Number-theory

文学与经典著作 Literary Works（出现示例）

• Introduction to Algorithms（CLRS，《算法导论》）：在数论/模运算相关内容中常用扩展欧几里得算法求模逆。
• Concrete Mathematics（《具体数学》）：在整数与数论技巧讨论中涉及欧几里得算法及其推广思路。
• The Art of Computer Programming, Vol. 2: Seminumerical Algorithms（Knuth，《计算机程序设计艺术》第二卷）：讨论整数算法与欧几里得算法相关方法。
• Handbook of Applied Cryptography（《应用密码学手册》）：在公钥密码体制与模逆计算处使用扩展欧几里得算法。
• An Introduction to Mathematical Cryptography（《数学密码学导论》）：讲解 RSA、同余与逆元时常明确使用扩展欧几里得算法。